package leetcode.recursive;

//79. 单词搜索
public class Exist {

    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }
        visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(i, j, 0, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int start, char[][] board, String word) {
        if (start == word.length() - 1) {
            return board[x][y] == word.toCharArray()[start];
        }
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, 1, -1, 0};
        if (board[x][y] == word.toCharArray()[start]) {
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int mx = dx[i] + x;
                int my = dy[i] + y;
                if (mx >= 0 && my >= 0 && mx < board.length && my < board[0].length
                        && !visited[mx][my]) {
                    if (dfs(mx, my, start + 1, board, word)) {
                        return true;
                    }
                }
            }
            visited[x][y] = false;
        }
        return false;
    }


}
